\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS259C Homework 1}
\newcommand{\myauthor}{Kevin Lewi}
\date{October 10, 2011}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 3}

\subsection*{Part A}

\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.5]{img1.png}
	\end{center}
	\caption{$E(\mathbb{R})$}
\end{figure}


\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.5]{img2.png}
	\end{center}
	\caption{$E(\mathbb{F}_{31})$}
\end{figure}

\subsection*{Part B}

The points of $E(\mathbb{F}_{31})$ are, listed in projective coordinates:
\[
[(0 : 0 : 1), (0 : 1 : 0), (1 : 11 : 1), (1 : 20 : 1), (2 : 0 : 1), (7 :
6 : 1), (7 : 25 : 1), (11 : 4 : 1), (11 : 27 : 1), (16 : 8 : 1), \]
\[ (16 :
23 : 1), (17 : 3 : 1), (17 : 28 : 1), (18 : 5 : 1), (18 : 26 : 1), (19 :
5 : 1), (19 : 26 : 1), (21 : 1 : 1), (21 : 30 : 1), \]
\[ (22 : 12 : 1), (22 :
19 : 1), (23 : 4 : 1), (23 : 27 : 1), (25 : 5 : 1), (25 : 26 : 1), (26 :
9 : 1), (26 : 22 : 1), (27 : 13 : 1), \] \[(27 : 18 : 1), (28 : 4 : 1), (28 :
27 : 1), (29 : 0 : 1)]
\]

\subsection*{Part C}

\note{todo: what is this question asking for?}

\subsection*{Part D}

For $P = (1,11)$ and $Q = (25,5)$, $a=9$ is such that $Q = [a]P$.

\subsection*{Part E}

\note{todo: not sure what pound sign means, but you can use 
next(underscore)prime() here, which is helpful.}

\section*{Problem 4}

\subsection*{Part A}

Let $P_1 = (x_1,y_1)$ be a point on $E$ with $y_1 = 0$. By the group law, $P_1 + 
P_2 = \infty$ if $P_1 = P_2$ and $y_1 = 0$. Thus, $2 P_1 = \infty$, which shows 
that $P_1$ has order $2$ since $\infty$ is the identity.

\subsection*{Part B}

Let $P_1 = (x_1,y_1)$ be a point on $E$ with $x_1 = 0$. Since $A = 0$, it can't 
be the case that $B = 0$, for otherwise, $4A^3 + 27B^2 = 0$, which is not 
allowed. Hence, $y_1 \neq 0$, and by the group law, the slope of the line $m = 
(3x_1^2 + A) / 2y_1 = 0$. This yields $2 P_1 = (m^2 - 2x_1, m(x_1 - (m^2 - 
2x_1)) - y_1) = (0,-y_1)$. Then, $3 P_1 = P_1 + 2 P_1$, and since $P_1$ and $2 
P_1$ lie on the same vertical line, we get that $3 P_1 = \infty$, which shows 
that $P_1$ has order $3$.

\section*{Problem 5}

\subsection*{Part A}

First, if the point is $\infty$, then it has order $1$. For a point $P \neq 
\infty$, we consider the line $L$ tangent to $E$ at $P$ to obtain $2P$. There 
must be one other point of contact between $L$ and $E$ (other than $P$), and 
this point is $2P$ (where, it is possible that $2P = \infty$ if $L$ was 
vertical). Now, note that when computing $P \boxplus 2P$, we use the same line 
$L$. The "third" point of contact is $P$ again, so we have that $P \boxplus P 
\boxplus P = P$, which proves that $P$ has order $2$. Thus, all points on the 
curve have order at most $2$.

\subsection*{Part B}

Assume to get a contradiction that there exists a unique identity $e$. Let $P_1 
\neq \infty$ be a point on $E$ whose tangent line $L_1$ is not vertical. Then, 
$P_1$ has order $2$, so $P_1 \boxplus P_1 = e$. Let $P_2$ be a point on $E$ 
whose tangent line $L_2$ is also not vertical and $L_1 \neq L_2$. Again, $P_2 
\boxplus P_2 = e$. Hence, $P_1 \boxplus P_1 = P_2 \boxplus P_2$, and so $P_1$ 
and $P_2$ must lie on the same line, tangent to both $P_1$ and $P_2$. This 
contradicts the assumption that $L_1 \neq L_2$.

\subsection*{Part C}

\note{todo}

\section*{Problem 6}

We can rewrite the generalized Weierstrass equation of (2.1) in the form of a 
monic quadratic $y^2 + (a_1 x + a_3) y - (x^3 + a_2 x^2 + a_4 x + a_6) = 0$. Let 
$P = (x_1,y_1) \neq \infty$. Then we know that one of the roots to this 
quadratic is $y_1$. Taking the hint provided, the other root must be $-a_1 x - 
a_3 - y$, and hence must correspond to the $y$-coordinate of $-P$. Since $-P$ 
and $P$ lie on the same vertical line, the $x$-coordinate of $P$ must equal the 
$x$-coordinate of $-P$. Thus, $-P = (x_1, -a_1 x_1 - a_3 - y_1)$ as desired.

\section*{Problem 7}

\note{just type up}

\section*{Problem 8}

\subsection*{Part A}

We first make the following claim: The function $\phi : (x,y) \to (x,-y)$ can be 
rewritten as $\phi : P \to P^{-1}$ which maps each point on the elliptic curve 
to its additive inverse (by the group law). To see this, note that by the second 
and fourth cases of the group law, $(x,y) + (x,-y) = \infty$, the identity.

By the above claim, it is also clear that $\phi$ maps points on $E$ to itself. 
It remains to show that $\phi$ is homomorphic. To see this, note that for any 
two points $P,Q \in E$,
\begin{align*}
	\infty &= \infty \\
	(P + Q) + (P + Q)^{-1} &= P + P^{-1} + Q + Q^{-1} \\
	&= (P + Q) + (P^{-1} + Q^{-1}) \\
	(P + Q)^{-1} &=  P^{-1} + Q^{-1} \\
	\phi(P + Q) &= \phi(P) + \phi(Q).
\end{align*}
Hence, we can conclude that $\phi$ is indeed a homomorphism from $E$ to itself.

\subsection*{Part B}

\note{todo}

\subsection*{Part C}

\note{todo}

\section*{Problem 9}

\note{todo.. doesn't seem too bad, just find the isos}

\section*{Problem 10}



\end{document}
